lib/Mi manual de algoritmos/version_world_finals_2009/src/geometria/segment_segment_intersection.cpp

   1 /*
   2   Returns true if point (x, y) lies inside (or in the border)
   3   of box defined by points (x0, y0) and (x1, y1).
   4 */
   5 bool point_in_box(double x, double y,
   6                   double x0, double y0,
   7                   double x1, double y1){
   8   return
   9     min(x0, x1) <= x && x <= max(x0, x1) &&
  10     min(y0, y1) <= y && y <= max(y0, y1);
  11 }
  12
  13 /*
  14   Finds the intersection between two segments (Not infinite
  15   lines!)
  16   Segment 1 goes from point (x0, y0) to (x1, y1).
  17   Segment 2 goes from point (x2, y2) to (x3, y3).
  18
  19   (Can be modified to find the intersection between a segment
  20   and a line)
  21
  22   Handles the case when the 2 segments are:
  23   *Parallel but don't lie on the same line (No intersection)
  24   *Parallel and both lie on the same line (Infinite
  25   *intersections or no intersections)
  26   *Not parallel (One intersection or no intersections)
  27
  28   Returns true if the segments do intersect in any case.
  29 */
  30 bool segment_segment_intersection(double x0, double y0,
  31                                   double x1, double y1,
  32
  33                                   double x2, double y2,
  34                                   double x3, double y3){
  35 #ifndef EPS
  36 #define EPS 1e-9
  37 #endif
  38
  39   double t0 = (y3-y2)*(x0-x2)-(x3-x2)*(y0-y2);
  40   double t1 = (x1-x0)*(y2-y0)-(y1-y0)*(x2-x0);
  41   double det = (y1-y0)*(x3-x2)-(y3-y2)*(x1-x0);
  42   if (fabs(det) < EPS){
  43     //parallel
  44     if (fabs(t0) < EPS || fabs(t1) < EPS){
  45       //they lie on same line, but they may or may not intersect.
  46       return (point_in_box(x0, y0,   x2, y2, x3, y3) ||
  47               point_in_box(x1, y1,   x2, y2, x3, y3) ||
  48               point_in_box(x2, y2,   x0, y0, x1, y1) ||
  49               point_in_box(x3, y3,   x0, y0, x1, y1));
  50     }else{
  51       //just parallel, no intersection
  52       return false;
  53     }
  54   }else{
  55     t0 /= det;
  56     t1 /= det;
  57     /*
  58       0 <= t0 <= 1 iff the intersection point lies in segment 1.
  59       0 <= t1 <= 1 iff the intersection point lies in segment 2.
  60     */
  61     if (0.0 <= t0 && t0 <= 1.0 && 0.0 <= t1 && t1 <= 1.0){
  62       double x = x0 + t0*(x1-x0);
  63       double y = y0 + t0*(y1-y0);
  64       //intersection is point (x, y)
  65       return true;
  66     }
  67     //the intersection points doesn't lie on both segments.
  68     return false;
  69   }
  70 }